#include <functional>
#include <iostream>
#include <random>
#include <vector>

template <typename T, typename Compare = std::greater<T>>
class Heap {
  public:
    // defalut the top is big
    Heap(T val, Compare com = Compare()) : datas{std::vector<T>{val}}, compare{com} {}
    Heap(Compare com = Compare()) : compare{com} {}

    void push_back(T val) {
        datas.push_back(val);
        int cur = datas.size() - 1;
        int parent = get_parent(cur);
        while (parent >= 0) {
            if (compare(datas[cur], datas[parent])) {
                std::swap(datas[cur], datas[parent]);
                cur = parent;
                parent = get_parent(cur);
            } else {
                break;
            }
        }
    }

    T top() { return datas.front(); }
    int get_parent(int index) { return (index + 1) / 2 - 1; }
    void pop() {
        std::swap(datas.front(), datas.back());
        datas.pop_back();
        auto i = 0;
        while (i * 2 + 2 < datas.size()) {
            if (compare(datas[i * 2 + 1], datas[i * 2 + 2])) {
            }
        }
    }

  private:
    Compare compare;
    std::vector<T> datas;
};

int main() {
    std::default_random_engine e;
    Heap<int, std::less<int>> h;
    for (int i = 0; i < 10; ++i) {
        int tmp = e() % 100;
        h.push_back(tmp);
        std::cout << h.top() << ", " << tmp << std::endl;
    }
}
